class MinOperationsToOne {
    public int minOperations(int[] nums) {
      int n = nums.length, cnt1 = 0, gcdAll = 0;
      for (int i = 0; i < n; i++) {
        cnt1 += nums[i] == 1 ? 1 : 0;
        gcdAll = gcd(gcdAll, nums[i]);
      }
      
      if(gcdAll > 1) return -1;
      if(cnt1 > 0){
        return n - cnt1;
      }
      int minSize = n;
      for (int i = 0; i < n; i++) {
          int g = 0;
          for (int j = i; j < n; j++) {
              g = gcd(g, nums[j]);
              if (g == 1) {
                  // 这里本来是 j-i+1，把 +1 提出来合并到 return 中
                  minSize = Math.min(minSize, j - i);
                  break;
              }
          }
      }
      return minSize + n - 1;
    }

    private int gcd(int a, int b) {
      if (a == 0) {
          return b;
      }
      return gcd(b % a, a);
    }

    public static void main(String[] args) {
        MinOperationsToOne obj = new MinOperationsToOne();
        int result = obj.minOperations(new int[]{1, 2, 3});
        System.out.println(result);
    }
}

// 给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

// 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。
// 请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

// 两个正整数的最大公约数指的是能整除这两个数的最大正整数。

 

// 示例 1：

// 输入：nums = [2,6,3,4]
// 输出：4
// 解释：我们可以执行以下操作：
// - 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
// - 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
// - 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
// - 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
// 示例 2：

// 输入：nums = [2,10,6,14]
// 输出：-1
// 解释：无法将所有元素都变成 1 。
 